Not applicable.
Not applicable.
This invention is in the field of data communications, and is more specifically directed to error protection in data communications.
Recent advances in the electronics field have now made high-speed digital data communications prevalent in many types of applications and uses. Digital communication techniques are now used for communication of audio signals for telephony, with video telephony now becoming available in some locations.
The quality of communications carried out in these ways depends upon the accuracy with which the received signals match the transmitted signals. Some types of communications, such as audio communications, can withstand bit loss to a relatively large degree. However, the communication of digital data, especially of executable programs, requires exact fidelity in order to be at all useful. Accordingly, various techniques for the detection and correction of errors in communicated digital bit streams have been developed. Indeed, error correction techniques have effectively enabled digital communications to be carried out over available communication facilities, such as existing telephone lines, despite the error rates inherent in high-frequency communication over these facilities.
Error correction may also be used in applications other than the communication of data and other signals over networks. For example, the retrieval of stored data by a computer from its own magnetic storage devices also typically utilizes error correction techniques to ensure exact fidelity of the retrieved data; such fidelity is, of course, essential in the reliable operation of the computer system from executable program code stored in its mass storage devices. Digital entertainment equipment, such as compact disc players, digital audio tape recorders and players, and the like also now typically utilize error correction techniques to provide high fidelity output.
An important class of error detection and error correction techniques is referred to as Reed-Solomon coding, and was originally described in Reed and Solomon, xe2x80x9cPolynomial Codes over Certain Finite Fieldsxe2x80x9d, J. Soc. for Industrial and Applied Mathematics, Vol. 8 (SIAM, 1960), pp. 300-304. Reed-Solomon coding uses finite-field arithmetic, such as Galois field arithmetic, to map blocks of a communication into larger blocks. In effect, each coded block corresponds to an over-specified polynomial based upon the input block. Considering a message as made up of k m-bit elements, a polynomial of degree nxe2x88x921 may be determined as having n coefficients; with n greater than k (i.e., the polynomial is overspecified), not all of the n coefficients need be valid in order to fully and accurately recover the message. According to Reed-Solomon coding, the number t of errors that may be corrected is determined by the relationship between n and k, according to   t  ≤                    n        -        k            2        .  
Reed-Solomon encoding is used to generate the encoded message in such a manner that, upon decoding of the received encoded message, the number and location of any errors in the received message may be determined.
Reed-Solomon decoding is especially beneficial in the detection and correction of random errors in a communicated bitstream. However, the limitation in the number of errors (i.e., the specified value t) that may be corrected by Reed-Solomon techniques precludes the correction of errors of a type referred to in the art as xe2x80x9cburst errorsxe2x80x9d. Burst errors refer to a contiguous error block in the communication channel, generally caused by effects in the communications facility, such as between the transmitting and receiving modems in a telephone communication implementation. Reed-Solomon techniques are generally unable to correct burst errors, because the number of errors in a given vector having a burst error is much greater than the Reed-Solomon correction limit t.
Convolutional interleaving is a conventional technique used to overcome this limitation of Reed-Solomon coding. In a general sense, convolutional interleaving operates by scrambling the time sequence of the transmitted bitstream from that of the conventional first-in-first-out sequence. At the receiving end, the received bitstream is then descrambled, or resequenced, to recover the transmitted message or data. Because of the scrambled sequence of the transmitted data, a burst error occurring within the scrambled bitstream over the communications facility will be dispersed over time. This reduces the density of the burst error in the actual transmitted message, permitting correction of the errors by subsequent Reed-Solomon decoding.
In general, convolutional interleaving introduces varying delay between adjacent codewords in a sequence, such that the temporal sequence of codewords, as transmitted, differs from the message sequence; an inversely varying delay is then introduced between received adjacent codewords, to restore the sequence. Attention is directed, in this regard, to FIG. 1 which illustrates the operation of conventional convolutional interleaving.
As shown in FIG. 1, demultiplexer 2 receives an input datastream on lines IN. This input datastream consists of a time series of symbols, each symbol containing M bits, according to the desired protocol. For example, conventional (204, 188, 8) Reed-Solomon coded transmissions generally operates according to eight-bit, or one byte, symbols (M=8). Demultiplexer 2 sequentially forwards symbols to N paths 5I0 through 5INxe2x88x921, of varying delay length. In this regard, demultiplexer 2 may be considered to include a buffering function, such that a vector of N symbols (or a multiple of N) is simultaneously applied to paths 5I. As described in Forney, xe2x80x9cBurst-Correcting Codes for the Classic Bursty Channelxe2x80x9d, IEEE Trans. on Communications Technology, Vol. COM-19, No. 5 (October 1971), use of convolutional interleaving in combination with downstream Reed-Solomon decoding is optimized using a number of paths that is equal to the size N of the Reed-Solomon block length. The symbol or symbols in this vector that are applied to path 5I0 immediately precede, in the time sequence on lines IN, the symbol or symbols applied to path 5I1, and so on. Each of paths 5I lead to transmission channel 4, within which the symbols are resequenced and over which the symbols are serially communicated.
The varying delay among paths 5I has a regular pattern in conventional convolutional interleaving. In the example of FIG. 1, path 5I0 involves no delay, such that the symbol or symbols applied thereto by demultiplexer 2 are immediately forwarded to transmission channel 4. Path 5I1 involves a delay of Bxe2x80x2 symbols, where Bxe2x80x2 corresponds to the number of symbols applied to each path 5I by demultiplexer 2 in a given vector; the symbol or symbols applied to path 5I1 in a first cycle are thus communicated to transmission channel 4 in the next cycle. Path 5I2 involves a delay of 2Bxe2x80x2, such that the symbol or symbols applied thereto in the first cycle are communicated to transmission channel 4 two cycles later, and so on, up until path 5Inxe2x88x921, which involves a delay of (Nxe2x88x921)Bxe2x80x2.
The number Bxe2x80x2 corresponds to the ratio of the total number of symbols communicated in a vector (B) to the number of symbols upon which the appropriate decoding technology (e.g., Reed-Solomon) operates (N). Typically, in the Reed-Solomon coding case, N symbols a recommunicated in a single vector, such that B=N, and thus Bxe2x80x2=1. In this case, therefore, N symbols are demultiplexed by demultiplexer 2 in a given operation, and one symbol is applied to each of N paths 5I0 through 5INxe2x88x921.
Because of the varying delays of N paths 5I, the system of FIG. 1 executes convolutional interleaving of the symbols to be communicated over transmission channel 4. Consider, for the sake of explanation, a communication system in which N=B=4, which presents symbols Sj,0 through Sj,3 in the jth communications cycle. The contents of the delay stages in paths 5I0 through 5I3 in this example would appear as follows:
In this arrangement, upon the application of the next symbol vector Sj to paths 5I from demultiplexer 2, the symbols Sj, 0, Sjxe2x88x921, 1, Sjxe2x88x922, 2, and Sjxe2x88x923, 3 will be applied to the transmission channel, and transmitted in that order. Accordingly, included in the sequence of transmitted signals over transmission channel 4, over time, will be the following symbols:
On the receiving end, the signals in this sequence are again placed in vector form, and are applied to output paths 5Q0 through 5QNxe2x88x921. According to this conventional convolutional interleaving approach inserts variable delay in each of output paths 5Q0 through 5QNxe2x88x921 between transmission channel and multiplexer 6, in an inverse manner relative to the delays of corresponding ones of paths 5I0 through 5INxe2x88x921. In this example, path 5Q0 inserts a delay of (Nxe2x88x921)Bxe2x80x2 symbols into the transmission path of the same symbols as communicated over path 5I0; similarly, path 5Q1 inserts a delay of (Nxe2x88x922)Bxe2x80x2 symbols, to which symbols communicated over path 5I1 are subjected. This arrangement continues, such that the sum of delays equals (Nxe2x88x921)Bxe2x80x2 symbols, for each pair of corresponding input path 5Ik and output path 5Qk. As a result, the vector presented by output paths 5Q to multiplexer 6 presents the symbols in sequence order. Using the same example of N=B=4 noted above, the contents of output paths 5Q following the receipt of the symbols transmitted by the above example of paths 5I are as follows:
In this example, therefore, the vector presented by paths 5Q0 through 5Q3 upon this cycle is [Sj,xe2x88x923 0, Sjxe2x88x923, 1, Sjxe2x88x923, 2, and Sjxe2x88x923, 3]. Through the operation of multiplexer 6, a data sequence of symbols Sj,xe2x88x923, 0, Sjxe2x88x923, 1, Sjxe2x88x923, 2, and Sjxe2x88x923, 3 are output on lines OUT, such symbols, of course, being in proper time sequence order.
The effects of convolutional interleaving may be seen from this example, considering that the most likely location of burst errors is present in transmission channel 4. Such burst errors, because of their density, could not be corrected by conventional error detection and correction techniques, if they were to occur over a series of symbols in their desired time sequence. However, because the time sequence of symbols communicated over transmission channel 4 is scrambled according to this conventional convolutional interleaving, any burst error will be spread out when presented on lines OUT by multiplexer 6. For example, consider the time sequence of symbols:
Consider a burst error in transmission channel 4 to affect four sequential symbols Sjxe2x88x924, 3, Sj, 0, Sjxe2x88x921, 1, Sjxe2x88x922, 2, so that the actual transmission sequence appears as:
Upon resequencing by output paths 5Q0 through 5Q3 and multiplexer 6, these errors will be spread out in time as follows:
As evident from this table, the burst errors are spread out over time. This dispersion of the burst error permits the application of error detection and correction techniques, such as Reed-Solomon decoding, to correct the errors caused by the burst event, such errors not being correctable in many cases without the effects of interleaving.
In its most rudimentary form, paths 5I and 5Q are implemented by way of digital shift registers. For the example of Bxe2x80x2=1, path 5I1 will thus include a single symbol shift register, path 5I2 will include a shift register of two symbol stages, and, accordingly, path 5Ik will include k symbol stages; conversely, output path 5Qk will include (Nxe2x88x921xe2x88x92k) symbol stages. However, as is known in the art, a shift register realization of a convolutional interleaving scheme is costly, both from the standpoint of chip area required and also from the standpoint of speed and power performance; in addition, the shift register realization necessitates the use of custom logic, and eliminates the ability to use a programmable logic device such as a digital signal processor (DSP) or general-purpose microprocessor. As a result, a memory implementation of the convolutional interleaving function is desirable.
As described in DAVIC 1.0 Specification Part 08 (Digital Audio-Visual Council, 1996), conventional convolutional interleaving is defined by the parameters of interleaver block length (I) and interleaving depth (D). Block length I is equal to or a submultiple of the Reed-Solomon code word length, and in this regard corresponds to the number of paths in the arrangement of FIG. 1. Interleaving depth D refers to the number of blocks to be maintained in the memory, and as such corresponds to the parameter B discussed above. This realization is of course useful in performing such convolutional interleaving through use of a programmable logic device, such as a DSP or microprocessor. As noted in the DAVIC specification, this memory implementation is realized in D times I bytes of memory (for eight-bit symbols), which is quite costly in chip area, especially in the case of large Reed-Solomon schemes. In addition, a straightforward implementation of the shift register function in memory necessitates repeated read/write cycles to effectively shift the symbols along the table, such repeated cycles being quite inefficient. While one may alternatively maintain a pointer, for each input path and output path, that points to the memory location to next be accessed, N such pointers would be required to implement either a transmitter or receiver interleaving circuit. The varying delay length in each of the memory-implemented input and output paths also renders the maintenance of such pointers extremely cumbersome and inefficient in processing time; in addition, extensive control logic is necessitated in order to effect the wrapping around of pointers of varying length.
It is therefore an object of the present invention to provide a memory-based method of effecting convolutional interleaving in an efficient manner.
It is a further object of the present invention to provide such a method in which the memory requirements are minimized.
It is a further object of the present invention to provide such a method in which the processing overhead required for maintenance of pointers is minimized.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.
The present invention may be implemented into a method of operating a programmable logic device to access memory in such a manner as to effect convolutional interleaving, either on the transmission or on the receive side. According to the present invention, the memory-implemented delay lines are paired with one another in such a manner as to be of substantially constant length. During a pass through the memory in a first direction, the oldest symbol in one of the paired delay lines is output and overwritten with the next symbol for that delay line, using a first pointer that is advanced upon completion of a pass in both directions. Upon completion of updating of the memory in the first direction, the oldest symbol in the other one of the paired delay lines is output and the newest symbol for that delay line is stored, using a second counter that advances upon completion of each delay line. As a result, delay lines of varying length are maintained in an efficient fashion. The present invention is suitable for both the transmission and receive sides of the communication.